#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include "CFG.h"
#include "TU.h"

static uint64_t TARJIndex;
static uint64_t TARJSCCIndex;
static __LinkedList *Stack;
static __LinkedList *SCCs;
static uint64_t TARJHotNodeThreshold;
static uint64_t TARJTransitionAccumulator;
static uint64_t TARJSignificantTransitionCounter;

#define MIN(A,B) ((A) < (B) ? (A) : (B))

static void StronglyConnect(CFGNode* Node){
    CFGEdge *Edge;
    CFGNode *W;
    __LinkedList *HotNodes;
    
    uint64_t HighestTransitionCount = 0;
    
    Node->TARJ_Index = TARJIndex;
    Node->TARJ_LowIndex = TARJIndex;
    
    TARJIndex++;
    
    LST_Push(Stack, Node);
    
    LST_Rewind(Node->Edges);
    
    while((Edge = LST_Next(Node->Edges))){
        
        if(Edge->Count <= 1)
            continue;
        
        if(Edge->Target->EpochExecutionCount){
            
            if(Edge->Count > HighestTransitionCount)
                HighestTransitionCount = Edge->Count;
            
            if(Edge->Count > 1)
                TARJTransitionAccumulator += Edge->Count,
                        TARJSignificantTransitionCounter++;
                
            if(!Edge->Target->TARJ_Index){
                StronglyConnect(Edge->Target);
                Node->TARJ_LowIndex = MIN(Node->TARJ_LowIndex, Edge->Target->TARJ_LowIndex);
            }
            else if(LST_Search(Stack, Edge->Target)){
                Node->TARJ_LowIndex = MIN(Node->TARJ_LowIndex, Edge->Target->TARJ_Index);
            }
        }
    }
    
    Node->TARJ_HighestTransitionCount = HighestTransitionCount;
    
    HighestTransitionCount = 0;
    
    if(Node->TARJ_LowIndex == Node->TARJ_Index){
        
        HotNodes = LST_New(NULL);
        
        printf("New SCC:\n");
        do{
            W = LST_Pop(Stack);
            
            HighestTransitionCount = W->TARJ_HighestTransitionCount >  HighestTransitionCount ?
                W->TARJ_HighestTransitionCount : HighestTransitionCount;
            
            if(W->TARJ_HighestTransitionCount > TARJHotNodeThreshold){
                LST_Insert(HotNodes, W);
            }
            
            printf("\t0x%04X\n", TU_GetStartingAddress(W->Unit));
            W->SCC_Index = TARJSCCIndex;
        }while(W != Node);
        
        W->SCC_HighestTransitionCount = HighestTransitionCount;
        W->SCC_HotNodes = HotNodes;
        LST_Insert(SCCs, W);
        TARJSCCIndex++;
        
        printf("\n");
        
    }
    
}

static int CompareCFGNodes(void* Data1, void* Data2){
    CFGNode* N1, *N2;
    
    N1 = Data1;
    N2 = Data2;
    
    return ((N1 == N2) ? 0 : 1);
}

void TARJAN_Init(void){
    TARJHotNodeThreshold = 50;
}

__LinkedList* TARJAN_Run(ControlFlowGraph* CFG){
    
    CFGNode* Node;
    
    TARJIndex = 1;
    TARJSCCIndex = 0;
    TARJSignificantTransitionCounter = 0;
    TARJTransitionAccumulator = 0;
    
    CFG_ResetCFGForTraversal(CFG);
    
    Stack = LST_New(CompareCFGNodes);
    
    SCCs = LST_New(NULL);
    
    LST_Rewind(CFG->NodeList);
    
    while((Node = LST_Next(CFG->NodeList))){
        if(Node->EpochExecutionCount){
            if(!Node->TARJ_Index){
                StronglyConnect(Node);
            }
        }
    }
    
    LST_Destroy(Stack);
    
    if(TARJSignificantTransitionCounter)
        TARJHotNodeThreshold = (((TARJTransitionAccumulator / TARJSignificantTransitionCounter) + TARJHotNodeThreshold) >> 1);
    
    printf("TARJHotNodeThreshold: %ld\n", TARJHotNodeThreshold);
    
    return SCCs;
}